class Solution 
{
public:
    int leastInterval(vector<char>& tasks, int n) 
    {
        unordered_map<char, int> task_occur;            // 任务发生的频率
        for (size_t i = 0;i < tasks.size(); i++)
        {
            ++task_occur[tasks[i]];
        }   

        vector<pair<int, int>> nextvalid_rest;          // 二元组：(任务开始的有效时间，剩余任务数)
        unordered_map<char, int>::iterator iter;
        for (iter = task_occur.begin(); iter != task_occur.end(); iter++)
        {
            nextvalid_rest.push_back(make_pair(1, iter->second));
        }

        int Time = 0;
        for(size_t i = 0; i < tasks.size(); i++)
        {
            ++Time;
            int minNextValid = INT_MAX;
            for (size_t j = 0; j < nextvalid_rest.size(); j++)
            {
                if (nextvalid_rest[j].second)
                {
                    minNextValid = min(minNextValid, nextvalid_rest[j].first);
                }
            }
            Time = max(Time, minNextValid);
            int best = -1;
            for (int j = 0; j < nextvalid_rest.size(); j++)
            {
                if (nextvalid_rest[j].second && nextvalid_rest[j].first <= Time)
                {
                    if(best==-1||nextvalid_rest[j].second>nextvalid_rest[best].second)
                    {
                        best=j;
                    }
                }
            }
            nextvalid_rest[best].first = Time + n + 1;
            --nextvalid_rest[best].second;
        }
        return Time;
    }
};